/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-20
 * Time: 6:36
 */
class Solution4 {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;

        int sum = 0;

        for(int x : stones) {
            sum += x;
        }

        int a = sum / 2;

        int[] dp = new int[a+1];

        for(int i = 1; i <= n; i++) {
            for(int j = a; j >= stones[i-1]; j--) {
                dp[j] =Math.max(dp[j-stones[i-1]]+stones[i-1],dp[j]);
            }
        }
        return sum - 2 * dp[a];
    }
}
